The present invention relates to routing in a packet switched network and more particularly to the generation and allocation of addresses for routing data in a packet switched network. The invention is applicable in particular, though not necessarily, to the generation and allocation of addresses in the Internet.
The Internet comprises a web of routers interconnected by transmission links (typically copper cables or optical fibres). Internet users typically connect their personal computers to the Internet via an access network such as a PSTN telephone network using a dial-up modem. The access network is in turn connected to the Internet via a Network Access Server (such as an Internet Service Provider). Other users may be connected to a Local Area Network (LAN) which is in turn connected directly to an Internet router.
The Internet is a packet switched network in which data to be transmitted is bundled into packets known as xe2x80x9cdatagramsxe2x80x9d. A datagram can carry a payload of variable length with the length being indicated in the datagram header. Each user is allocated a unique IP address comprising a prefix portion (i.e. MSBs) which identifies the network to which the user is connected and a suffix portion (i.e. LSBs) which identifies the user to that network. Each datagram is accompanied by the IP address of the destination user (as well as the IP address of the originating user), and the datagram is routed to the destination user by intervening routers in accordance with that IP address.
The current IPv4 standard defines IP addresses which are 4 octets (32 bits) long. Address ranges are allocated to networks by the US authority INTERNIC, with networks typically allocating individual IP addresses to users dynamically, as and when users request an Internet connection. The growth in the availability and use of the Internet in the last few years has been enormous and there are proposals to introduce an IPv6 standard defining 16 octet long EP addresses. It is hoped that this will prove sufficient to cope with future growth in the Internet.
A number of problems are inherent in the current Internet address generation and allocation process and which are unlikely to be overcome by the introduction of IPv6.
A first problem is that the allocation of addresses at the top level is made by a single authority (INTERNIC). This may lead to inequities and certainly causes delays and increased administrative responsibilities when introducing a new network. A related problem arises because addresses are allocated dynamically to users by a network, adding a time delay to a user""s internet connection time. Moreover, it can be difficult for a user to identify the IP address allocated to some other user with whom that first user wishes to communicate because of this dynamic allocation of IP addresses.
There is often a need to enter IP addresses manually into users"" computers, servers, routers, etc. There is an obvious possibility for errors in such manual data entry operations.
It will be appreciated that these problems are not only limited to the Internet but also arise in other heavily used packet switched networks including Wide Area Networks (WANs) and mobile telecommunications networks.
It is an object of the present invention to overcome or at least mitigate the disadvantages noted in the preceding paragraphs. This and other objects are achieved by generating addresses for packet switched network users on the basis of the geographical location of the users.
According to a first aspect of the present invention there is provided a method of allocating an address to a user of a packet switched network, where the address is used to route data packets over the network from a remote location to the user, the method comprising determining the geographical location of the user and generating an address on the basis of the determined geographical location.
It will be appreciated that, subject to the resolution with which a user""s location is determined, each user or set of users may be allocated a unique address within the data network. Address allocation is no longer the responsibility of a single authority but rather becomes an inherent property of a user""s location. The generated address corresponds to or is mathematically derivable from the determining geographical location.
The present invention facilitates the sending of location specific data packets. That is to say that providing the (approximate) location of a user is known it is possible to communicate with that user.
Preferably, the packet switched network is an EP network comprising a plurality of routers which route data packets in accordance with destination IP addresses which accompany the datagrams (or other data derived from the destination IP addresses). More preferably, the data network is the Internet.
Preferably, said step of determining the geographical location of the user comprises using a Global Positioning System (GPS) receiver to determine the longitude and latitude (and optionally the altitude) of the user. Alternatively, the location of the user may be determined using two or more fixed terrestrial stations. For example, a user""s location may be determined using measurements made by a mobile telephone device and a mobile telecommunications network.
According to a second aspect of the present invention there is provided apparatus for use in allocating an address to a user of a packet switched network, the apparatus comprising input means for receiving the geographical location of the user and processing means for generating an address on the basis of the received geographical location.
Preferably, said processing means is arranged to generate a packet header containing said geographical location. In use, the packet header also contains the geographical location of the destination for a packet.
According to a third aspect of the present invention there is provided a device for accessing a packet switched data network, the device comprising:
position determining means for determining the geographical location of the device; and
apparatus comprising input means for receiving the geographical location of the device and processing means for generating an address on the basis of the received geographical location.
Whilst the present invention may be employed with existing packet switched network architectures, it makes possible the introduction of an entirely new architecture which offers significant advantages.
According to a fourth aspect of the present invention there is provided a packet switched data network comprising a multiplicity of interconnected routers each of which has a knowledge of its own geographical location as well as the geographical locations of its neighbouring routers, and each of the routers being arranged in use to route a received data packet to a neighbouring router on the basis of its own location, the locations of the neighbouring routers, and geographical destination/routing information contained in the data packet.
Embodiments of the above fourth aspect of the invention give rise to a number of significant advantages over existing packet switched networks. These include avoiding the need to continuously update routing tables of the routers (reducing network traffic), accelerating the routing process as the need to examine lengthy routing tables is avoided, and a reduction in the complexity of routers.
Preferably, said multiplicity of routers comprises a first set of north/south sub-routers and a second set of east/west sub-routers, at least some of the routers of both sets being interconnected to allow the direction of a data packet to be switched from north/south to east/west and vice versa.
Preferably, each router is arranged to examine a Current Direction Indicator contained in a received data packet to determine the current transmission direction of the packet. Each router also examines a distance counter contained in a received data packet, and which indicates the distance which the packet has travelled in the indicated direction or the remaining transmission distance in that direction. In the event that a distance counter indicates that the receiving router is the destination router (e.g. is the router which serves the destination user) in the indicated direction, the router either causes the direction to be switched, from north/south to east/west and vice versa, or causes the packet to be sent to a user connected to the router.
According to a fifth aspect of the present invention there is provided a method of routing a data packet in a packet switched network, the method comprising the steps of:
a) generating a data packet header containing at least the longitudes and latitudes of the source and destination of the data packet, the header also containing a direction indicator indicating the direction of transmission of the packet and a distance counter indicating the distance travelled by the packet in the indicated direction or the remaining distance in that direction;
b) sending the data packet in the indicated direction to a neighbouring router and updating the distance counter;
c) examining the data packet header at the receiving router to determine whether or not the receiving router represents the destination router in the indicated direction;
d) if not, then sending the data packet in the indicated direction to a neighbouring router and updating the distance counter; and
e) if yes, then updating the direction indicator with an indicator orthogonal to the original indicator and calculating a new distance counter indicating the distance travelled by the packet in the new indicated direction or the remaining distance in that direction, and repeating steps b) to d) until the receiving router represents the destination router in the indicated direction.
According to a sixth aspect of the present invention there is provided a method of allocating an address to a mobile station of a cellular telecommunications network, where the address is used to route data packets over the network from a remote location to the mobile station, the method comprising generating an address on the basis of the geographical location of a node of the network to which the mobile station is connected.
In a GSM network, the node may be a base station or a base station controller or an MSC. In a UMTS network, the node may be a base station, RNC, MSC, SGSN, etc.